function TreeNode(val = 0) {
    this.left = -1   // 区间左边界
    this.right = -1  // 区间右边界
    this.val = val   // 节点值（区间值）
    this.lazy_tag = null  // 区间和问题的延迟更新标记
}

function SegmentTree(arr, func) {
    this.init(arr, func)
}

SegmentTree.prototype.init = function (arr, func) {
    this.size = arr.length
    this.tree = new Array(4 * this.size).fill(0).map(_ => new TreeNode())
    this.arr = arr // 原始数据
    this.func = func // func是一个函数，左右区间的聚合方法
    if (this.size > 0) {
        this.build(0, 0, this.size - 1)
    }
}

// -------------------------------------------------------------------构建线段树，节点的存储下标为index，节点的区间为[left, right]
SegmentTree.prototype.build = function (index, left, right) {
    this.tree[index].left = left
    this.tree[index].right = right
    if (left === right) {
        // 叶子节点，节点值为对应位置的元素值
        this.tree[index].val = this.arr[left]
        return
    }
    let mid = left + Math.floor((right - left) / 2) // 左右节点划分点
    let left_index = index * 2 + 1 // 左节点的存储下标
    let right_index = index * 2 + 2 // 右节点的存储下标
    this.build(left_index, left, mid) // 递归创建左子树
    this.build(right_index, mid + 1, right) // 递归创建右子树
    this.pushup(index)

}


// 向上更新下标为index的节点区间值，节点区间值等于该节点左右节点元素值的聚合计算结果
SegmentTree.prototype.pushup = function (index) {
    let left_index = index * 2 + 1 // 左节点的存储下标
    let right_index = index * 2 + 2 // 右节点的存储下标
    this.tree[index].val = this.func(this.tree[left_index].val, this.tree[right_index].val)
}

// --------------------------------------------------------------------------------------单点更新将arr[i]更改为val
SegmentTree.prototype.update_point = function (i, val) {
    this.arr[i] = val
    this._update_point(i, val, 0, 0, this.size - 1)
}

// 单点更新，将arr[i]更改为val
SegmentTree.prototype._update_point = function (i, val, index, left, right) {
    if (this.tree[index].left === this.tree[index].right) {
        this.tree[index].val = val
        return
    }
    let mid = left + Math.floor((right - left) / 2) // 左右节点划分点
    let left_index = index * 2 + 1 // 左节点的存储下标
    let right_index = index * 2 + 2 // 右节点的存储下标
    if (i <= mid) {
        // 在左子树中更新节点值
        this._update_point(i, val, left_index, left, mid)
    } else {
        // 在右子树中更新节点值
        this._update_point(i, val, right_index, mid + 1, right)
    }
    this.pushup(index)
}

// ----------------------------------------------------------------------------------区间查询，查询区间为[q_left, q_right]
SegmentTree.prototype.query_interval = function (q_left, q_right) {
    return this._query_interval(q_left, q_right, 0, 0, this.size - 1)
}

SegmentTree.prototype._query_interval = function (q_left, q_right, index, left, right) {
    if (left >= q_left && right <= q_right) {
        // 节点所在区间被查询区间覆盖，直接返回节点值
        return this.tree[index].val 
    }
    if (right < q_left || left > q_right) {
        // 节点所在区间与查询区间无关
        return 0
    }
    this.pushdown(index)

    let mid = left + Math.floor((right - left) / 2) // 左右节点划分
    let left_index = index * 2 + 1 // 左子节点的下标
    let right_index = index * 2 + 2 // 右子节点的下标
    let res_left = 0 // 左子树查询结果
    let res_right = 0 // 右子树查询结果
    if (q_left <= left) {
        res_left = this._query_interval(q_left, q_right, left_index, left, mid)
    }
    if (q_right > mid) {
        res_right = this._query_interval(q_left, q_right, right_index, mid + 1, right)
    }
    return this.func(res_left, res_right) // 返回左右子树元素值的聚合计算结果
    

}


// ----------------------------------------------------------------------------------------区间更新
SegmentTree.prototype.update_interval = function (q_left, q_right, val) {
    this._update_interval(q_left, q_right, val, 0, 0, this.size - 1)
}

SegmentTree.prototype._update_interval = function (q_left, q_right, val, index, left , right) {
    if (left >= q_left && right <= q_right) {
        // 节点所在区间被查询区间覆盖，直接返回节点值
        let interval_size = right - left + 1  // 当前节点所在区间大小
        this.tree[index].val = interval_size * val // 当前节点所在区间每个元素都改为val
        this.tree[index].lazy_tag = val // 将当前节点的延迟标记为区间值
        return
    }
    if (right < q_left || left > q_right) {
        // 节点所在区间与查询区间无关
        return 0
    }
    this.pushdown(index)

    let mid = left + Math.floor((right - left) / 2) // 左右节点划分
    let left_index = index * 2 + 1 // 左子节点的下标
    let right_index = index * 2 + 2 // 右子节点的下标
    if (q_left <= left) {
        this._update_interval(q_left, q_right, val, left_index, left, mid)
    }
    if (q_right > mid) {
        this._update_interval(q_left, q_right, val, right_index, mid + 1, right)
    }
    this.pushup(index)




}



// 向下更新下标为index的节点所在区间的左右子节点的值和懒惰标记
SegmentTree.prototype.pushdown = function (index) {
    let lazy_tag = this.tree[index].lazy_tag
    if (!lazy_tag) {
        return
    }
    let left_index = index * 2 + 1  // 左子节点存储下标
    let right_index = index * 2 + 2 // 右子节点存储下标

    this.tree[left_index].lazy_tag = lazy_tag // 更新左子节点懒惰标记
    let left_size = this.tree[left_index].right - this.tree[left_index] + 1
    this.tree[left_index].val = lazy_tag * left_size // 更新左子节点值

    this.tree[right_size].lazy_tag = lazy_tag // 更新右子节点懒惰标记
    let right_size = this.tree[right_index].right - this.tree[right_index] + 1
    this.tree[right_index].val = lazy_tag * right_index // 更新右子节点值

    this.tree[index].lazy_tag = null  // 更新当前节点的懒惰标记

}


let arr = [1, 2, 3, 4, 5]
function func(a, b) {
    return a + b
}
let tree = new SegmentTree(arr, func)

tree.update_point(4, 6)
console.log(tree)